/*
 * FileName: depthfirstsearch.cc
 * Author: 李波(Edwin Lee)
 * Date: 2024-07-18 15:34:55
 * Version: 1.0
 * Description:二维迷宫深度优先算法 
 */
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const char RIGHT = 1;
const char DOWN = 2;
const char LEFT = 4;
const char UP = 8;

class Maze
{
public:
	Maze():row_(0),col_(0),pmaze_(nullptr){}
/*
	Maze(int row, int col)
		:row_(row)
		,col_(col)
		,pmaze_(nullptr)
	{
		initMaze(row,col);
	}
*/
	void initMaze(int row, int col)
	{
		if(nullptr != pmaze_)
		{
			for(int i=0; i < row_; ++i)
			{
				delete []pmaze_[i];
			}
			delete []pmaze_;
		}

		row_ = row;
		col_ = col;
		srand(time(nullptr));
		pmaze_ = new Node*[row];
		for(int i = 0; i < row; ++i)
		{
			pmaze_[i] = new Node[col];
			for(int j = 0; j < col; ++j)
			{
				pmaze_[i][j].x_ = i;
				pmaze_[i][j].y_ = j;
				pmaze_[i][j].val_ = rand()%2;
			}
		}
	}

	void showMaze()
	{
		cout<<"-------------showMaze begin-----------"<<endl;
		for(int i=0; i<row_; ++i)
		{
			for(int j=0; j<col_; ++j)
			{
				cout<<pmaze_[i][j].val_<<" ";
			}
			cout<<endl;
		}
		cout<<"--------------showMaze end------------"<<endl;
	}

	void searchMazePath()
	{
		int i = 0;
		int j = 0;
		if(pmaze_[0][0].val_ == 1)
		{
			cout<<"没有找到迷宫出口"<<endl;
			return;
		}
		for(;;)
		{
			if(!(pmaze_[i][j].state&RIGHT))
			{
				pmaze_[i][j].state |= RIGHT;
				stack_.push(pmaze_[i][j]);
				if(i+1==row_ && j+1==col_)
				{
					cout<<"找到了迷宫出口"<<endl;
					showPath();
					return;
				}

				if(j+1==col_ || pmaze_[i][j+1].val_==1)
				{
					continue;
				}
				else 
				{
					++j;
					continue;
				}
			}

			if(!(pmaze_[i][j].state&DOWN))
			{
				pmaze_[i][j].state |= DOWN;
				if(i+1==row_ || pmaze_[i+1][j].val_==1)
				{
					continue;
				}
				else 
				{
					++i;
					continue;
				}
			}

			if(!(pmaze_[i][j].state&LEFT))
			{
				pmaze_[i][j].state |= LEFT;
				if(j==0 || pmaze_[i][j-1].val_==1)
				{
					continue;
				}
				else 
				{
					--j;
					continue;
				}
			}

			if(!(pmaze_[i][j].state&UP))
			{
				pmaze_[i][j].state |= UP;
				if(i==0 || pmaze_[i-1][j].val_==1)
				{
					stack_.pop();
					if(stack_.empty())
					{
						cout<<"没有找到迷宫出口"<<endl;
						break;
					}
					i = stack_.top().x_;
					j = stack_.top().y_;
					continue;
				}
				else 
				{
					--i;
					continue;
				}
			}
			stack_.pop();
			if(stack_.empty())
			{
				cout<<"没有找到迷宫出口"<<endl;
				break;
			}
			i = stack_.top().x_;
			j = stack_.top().y_;
		}
	}


//private:
	void showPath()
	{
		if(!path_.empty())
			path_.clear();
		for(int i=0; i<row_; ++i)
		{
			path_.push_back(string());
			for(int j=0; j<col_; ++j)
			{
				path_.back().push_back((char)(pmaze_[i][j].val_+'0'));
				path_.back().push_back(' ');
			}
		}
		
		while(!stack_.empty())
		{
			path_[stack_.top().x_][stack_.top().y_*2] = '*';
			stack_.pop();
		}

		for(string& str:path_)
		{
			cout<<str<<endl;
		}
	}

private:
	struct Node 
	{
		int x_;
		int y_;
		int val_;
		char state=0;
	};
	
	int row_;
	int col_;
	Node** pmaze_;
	stack<Node> stack_;
	vector<string> path_;
};

int main()
{
	cout<<"----------main begin------------"<<endl;
	Maze maze;
	maze.initMaze(5, 5);
	maze.showMaze();
	maze.searchMazePath();
	maze.initMaze(10, 8);
	maze.showMaze();
	maze.searchMazePath();
	return 0;
}
